In a packet switched communications network, when a first user sends a message to a second user, many things occur. First, the message is divided into smaller units of the message. Next, each smaller unit of message, also referred to as a payload, is combined with a “header.” The header may contain various types of information such as a message source, a message destination, and other information (or any combination thereof). The combination of a header and a payload forms a “packet” of information.
Each node of a packet switched network attempts to ensure that any packet it receives is, eventually, sent to the intended node (i.e., a node associated with the second user). The packet may have to travel through numerous nodes in order to reach its final destination. Each time a packet travels from one node to another, it is said to have “hopped” from node to node. Once all the packets of a particular message are received at the destination node, the packets are “decoded” and assembled into the original message. The second user may then view the message.
A primary goal of packet switched communications networks is to minimize the time delay between the sending and the receiving of a message. One factor contributing to the time delay is the number of hops a packet must make prior to arriving at its destination node. Thus, many people have attempted to reduce the number of hops a packet must make when going from a source node to a destination node. The sequence of nodes, or, equivalently, the sequence of links, through which all packet must travel when going from a source node to a destination node are specified and, collectively, referred to as the “communications path” (“CP”). One or more CPs are specified for each combination of source-destination nodes. Examples of network technologies that use CPs as their mean for transferring packets include Internet Protocol (IP) networks with Multi-Protocol Label Switching (MPLS) technology and Asynchronous Transfer Mode (ATM) networks. Chapter 6 of G. C. Sackett and C. Y. Metz, ATM and Multi-protocol Networking, McGraw-Hill, New York, 1997 and T. Li, MPLS and the Evolving Internet Architecture, IEEE Communications Magazine, 37 No 12, 38–41, December 1999 are a sample of general references on ATM and IP-MPLS networks.
CPs are changed over time primarily due to congestion or failures detected on certain network elements. The changes in the CPs are executed either automatically by the switches or routers, or by external traffic control software. Over time, the changes in these CPs may lead to excessively long CPs, which adversely affect the network performance in multiple ways. These excessively long CPs are referred to as out-of-kilter paths (“OKPs”). CPs that are not excessively long are referred to as in-kilter paths (“IKP”). When CPs are out-of-kilter, network resources are used inefficiently, which, in turn, require additional capital investments in order to expand capacity on various links and nodes. More importantly, the end-to-end performance, in terms of expected packet delay, jitter and loss, may deteriorate and become unacceptable to customers. Network service providers may violate their Service Level Agreements (“SLAs”) with customers, which may result in significant monetary refunds and/or loss of customers.
The importance of limiting the number of hops of CPs has arisen in a variety of routing contexts. Representative references include G. R. Ash, R. H. Cardwell, and R. P. Murray, Design and Optimization of Networks With Dynamic Routing, The Bell System Technical Journal, 60, 1787–1820, 1981 for circuit-switched networks, K. Kompella and D. Awduche, Notes on Path Computation in Constraint-Based Routing, Internet Engineering Task Force (IETF), Network Working Group Internet Draft, draft-kompella-te-pathcomp-00.txt, 2000 and S. Christensen, Voice Over IP Solutions, White Paper, 2000-11-001, Juniper Networks, June 2001 for packet switched networks, and R. M. Krishnaswamy and K. N. Sivarajan, Design of Logical Topologies: A Linear Formulation for Wavelength-Routed Optical Networks With no Wavelength Changers, IEEE/ACM Transactions on Networking, 9, 186–198, 2001 for optical networks. CPs with a bounded number of hops also arise in network design models. This is explained in, for example, A. Balakrishnan and K. Altinkemer, Using a Hop-Constrained Model to Generate Alternative Communication Network Design, ORSA Journal on Computing, 4, 192–205, 1992 and D. Bienstock and I. Saniee, ATM Network Design: Traffic Models and Optimization-Based Heuristics, Telecommunication Systems, 16, 399–421, 2001.
A CP is characterized as either an OKP or as an IKP. The definition of an OKP is a CP that has too many hops. The number of hops of a CP may be too many if, for example, it exceeds a predetermined number. As another example, the number of hops of a specified CP may be too many if it exceeds a predetermined multiplier of the number of hops in the shortest path (in terms of hops) between the source and destination nodes of that CP. Other ways of determining if a CP has too many hops will be apparent to those skilled in the art. CPs that are not OKPs are IKPs. The method for reassigning OKPs is independent of the definition used to divide between OKPs and IKPs. Any OKP that is reassigned will be in-kilter after the reassignment, and any IKP that is reassigned will remain in-kilter after the reassignment. Reassignment of IKPs is permitted in order to generate spare capacity on certain network links so that more OKPs can be reassigned.
Typically, multiple CPs need to be reassigned. These reassignments are executed in a sequence, one at a time. Hence, it is important not only to determine the set of CPs that should be reassigned, but also the ordered sequence in which these CPs should be reassigned. Even if capacity constraints are satisfied upon completion of all reassignments on all network links, temporary capacity violation may incur after the execution of any subset of these reassignments, unless the method explicitly prevents such violations. Also, a CP should be reassigned in one piece into a single new route rather than be split onto multiple routes. The recommended sequence of reassignments approximately optimizes a predefined objective such as, but not limited to, maximizing the number of reassigned OKPs or maximizing the total load reassigned from OKPs to IKPs.
There are numerous methods that determine CPs. For example, R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, Englewood Cliffs, N.J., 1993 (hereinafter “Ahuja”) disclose, in chapter 17, models that deal with routing point-to-point demands in a network subject to link capacity constraints. These are well studied models and known in the literature as multi-commodity network flow models. CP reassignments can be formulated using the path formulation for such models by appropriately setting of cost parameters to the paths. However, these models have shortcomings. They do not provide an ordered sequence of reassignments and, thus, the solution may incur temporary capacity violations; and the existing CPs may be split to multiple new routes.
T. Carpenter, K. R. Krishnan, and D. Shallcross, Enhancements to Traffic Engineering for Multi Protocol Label Switching, in (editors: J. M. De Souza, N. L. S. Da Fonseca and E. A. De Souza E Silva) Teletraffic Engineering in the Internet Era, Proceeding of the International Teletraffic Congress-ITC 17, Salvador de Bahia, Brazil, September, 2001, Elsevier, Amsterdam, 2001 (Volume 4, 529–540) (hereinafter “Carpenter”) describe variations of multi-commodity network flow models to determine CPs, called Label-Switched Paths, for IP networks with MPLS. However, as Carpenter is based on standard multi-commodity network flow models, it has the same shortcomings specified above, namely, temporary capacity violations may occur and CPs may be split onto multiple routes. Carpenter mentions the importance of not splitting CPs and proposes to solve first a network flow model which allows splitting and then, using the results, to solve a restricted version of the flow model with integer variables. However, as Carpenter observes, the restricted problem may still be very difficult to solve and may lead to solutions that are not close to optimal.